package leetcode.doublepointer;

import java.util.Stack;

//42. 接雨水
public class Trap {
    public static void main(String[] args) {
        int[] data = {4, 3, 2, 0, 1, 1, 5};
        System.out.println(trap(data));
    }

    //单调栈----单调递减---当前元素小于栈顶元素时，可以进栈
    public static int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int water = 0;
        //特殊情况
        if (height.length < 3) {
            return 0;
        }
        for (int i = 0; i < height.length; i++) {
            //栈顶元素

            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int popnum = stack.pop();
                //计算该层的水的单位
                if (!stack.isEmpty()) {
                    int temp = height[stack.peek()];//栈顶元素值
                    //高----用需要并已经出栈的元素的前后两个元素分别减去当前已经出栈的元素，看看哪个小，
                    //类似木桶理论
                    int high = Math.min(temp - height[popnum], height[i] - height[popnum]);
                    //宽---用当前元素减去当前已经出栈的元素的前一个元素再减一
                    int width = i - stack.peek() - 1;
                    water += high * width;
                }

            }
            //入栈的是索引
            stack.push(i);
        }
        return water;

    }


    //dp
    public static int trap2(int[] height) {
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        if (n == 0) {
            return 0;
        }
        // 记录每个柱子左边柱子最大高度
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        // 记录每个柱子右边柱子最大高度
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int count = Math.min(leftMax[i], rightMax[i]) - height[i];
            if (count > 0) {
                sum += count;
            }
        }
        return sum;
    }
}
